1. Technical Field
The invention disclosed broadly relates to semiconductor circuits and, more particularly, it relates to an improved integrated circuit for random number generation.
2. Background Art
The availability of high quality random number generators is essential to the effectiveness of a cryptographic system. With the advent of very large scale integrated circuits (VLSI), and the embodiment of cryptographic systems in VLSI, it is important that component random number generators be compatible with VLSI circuit processing. Various pseudo-random number generators have been developed in the prior art, however they are all subject to attack by an eavesdropper with the intention of circumventing the cryptographic system.
One approach in the prior art to random number generation is the use of linear feedback shift registers. For example, in the book by S. W. Glomb, "Shift Register Sequences," Holden-Day, Inc., San Francisco, 1967, describes maximum length linear feedback shift registers which satisfy several criteria for randomness. Three of those criteria are, first, that in every period, the number of ones and the number of zeros do not differ by more than one. A second criterion is that in every period half the runs have a length of one, one-fourth of the runs have a length of two, one-eighth of the runs have a length of three, and so on. Furthermore, for each of these run lengths, there are as many runs of zeros as there are runs of ones. A third criterion is that the auto-correlation function is unity for a zero shift, and minus one/n for all other shifts (n being the number of shift register stages).
As Glomb and others have pointed out, the linear feedback shift register sequence is inherently periodic, which makes the output of the shift register not truly random, but only pseudo-random. Although this diminishes its utility as a component of a cryptographic system, it has been the practice in the prior art to increase the duration of the period by using a sufficiently large number of stages in the linear feedback shift register. For example, a sixty-four bit, maximum length feedback shift register, running at a clocked frequency of one MH, would not repeat itself for 585,000 years.
However, in cryptographic applications, the linear feedback shift register approach is vulnerable to attack because it is deterministic. All future and all past states can be predicted when the present state of the shift register is known. While it is true that the resulting output of the prior art linear feedback shift registers has superior statistical qualities its result is, unfortunately, totally predictable.